#pragma once

#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<cassert>
using namespace std;

enum Color{ RED, BLACK};
template<class K, class V>
struct RBTreeNode {
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;


	K _key;
	V _value;

	Color _color;

	RBTreeNode(const K& key = K(), const V& value = V())
		:_key(key), _value(value), _left(nullptr),
		_right(nullptr), _color(RED), _parent(nullptr){
	}

};

template<class K, class V>
class RBTree {
	typedef RBTreeNode<K, V> Node;

public:

	RBTree() :_root(nullptr) {}
	RBTree(const RBTree& tree)
	{
		_root = Copy(tree._root);
	}

	RBTree& operator=(const RBTree& tree)
	{
		return BSTree(tree);
	}
	~RBTree()
	{
		Destroy(_root);
		_root = nullptr;
	}
	bool Insert(const K& key, const V& value) {

		Node* newNode = new Node(key, value);
		if (_root == nullptr) {
			_root = newNode;
		}
		else {
			Node* parent = _root;
			Node* cur = _root;

			while (cur) {
				parent = cur;
				if (key < cur->_key) cur = cur->_left;
				else if (key > cur->_key) cur = cur->_right;
				else return false;
			}

			if (key < parent->_key) {
				parent->_left = newNode;
			}
			else {
				parent->_right = newNode;
			}
			newNode->_parent = parent;
			cur = newNode;

			while (parent != nullptr && parent != _root && parent->_color == RED){
				Node* grandFather = parent->_parent;
				Node* uncle = (parent == grandFather->_left ? grandFather->_right : grandFather->_left);

				if (uncle != nullptr && uncle->_color == RED){
					parent->_color = uncle->_color = BLACK;
					grandFather->_color = RED;

					cur = grandFather;
					parent = grandFather->_parent;
				}
				else {//(uncle == nullptr || uncle->_color == BLACK)
					
					if (parent == grandFather->_left ){
						//     g
						//   p   u
						// c
						if (cur == parent->_left){
							RotateR(grandFather);

							parent->_color = BLACK;
							grandFather->_color = RED;
						}
						//     g
						//   p   u
						//     c
						else{
							RotateLR(grandFather);
							grandFather->_color = RED;
							cur->_color = BLACK;
						}

					}
					else {
						//     g
						//   u   p
						//         c
						if (cur == parent->_right){
							RotateL(grandFather);
							parent->_color = BLACK;
							grandFather->_color = RED;
						}
						//     g
						//   u   p
						//     c
						else{
							RotateRL(grandFather);
							grandFather->_color = RED;
							cur->_color = BLACK;
						}
					}
					break;
				}
			}

		}

		_root->_color = BLACK;
		return true;
	}

	Node* Find(const K& key)
	{

		Node* cur = _root;
		while (cur)
		{
			if (key < cur->_key) cur = cur->_left;
			else if (key > cur->_key) cur = cur->_right;
			else return cur;
		}
		return nullptr;
	}

	bool Erase(const K& key)
	{
		if (_root == nullptr) return false;
		Node* parent = _root;
		Node* cur = _root;

		while (cur && cur->_key != key) {
			parent = cur;
			if (key < cur->_key) cur = cur->_left;
			else  cur = cur->_right;
		}
		if (cur == nullptr) return false;

		if (cur->_right == nullptr) {
			if (cur == parent->_left) {
				parent->_left = cur->_left;
			}
			else if (cur == parent->_right) {
				parent->_right = cur->_left;
			}
			else if (cur == _root)
			{
				_root = cur->_left;
			}
			else
			{
				assert(false);
			}
			delete cur;
		}
		else if (cur->_left == nullptr) {
			if (cur == parent->_left) {
				parent->_left = cur->_right;
			}
			else if (cur == parent->_right) {
				parent->_right = cur->_right;
			}
			else if (cur == _root)
			{
				_root = cur->_right;
			}
			else
			{
				assert(false);
			}

			delete cur;
		}
		else {
			Node* leftMaxParent = cur;
			Node* leftMax = cur->_left;
			while (leftMax->_right) {
				leftMaxParent = leftMax;
				leftMax = leftMax->_right;
			}
			swap(cur->_key, leftMax->_key);
			swap(cur->_value, leftMax->_value);

			if (leftMax == leftMaxParent->_left) {
				leftMaxParent->_left = leftMax->_left;
			}
			else {
				leftMaxParent->_right = leftMax->_left;
			}

			delete leftMax;
		}

		cout << ":" << key << endl;
		return true;
	}

	void InOrder()
	{
		_InOrder(_root);
	}
	bool Empty()
	{
		return _root == nullptr;
	}

	bool IsBalance()
	{

		int blackNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_color == BLACK)blackNum++;
			cur = cur->_right;
		}
		return _IsBalance(_root, blackNum,  0);
	}
private:
	void Destroy(Node* root)
	{
		if (root == nullptr) return;

		Destroy(root->_left);
		Destroy(root->_right);

		delete root;
		root = nullptr;
	}
	Node* Copy(Node* root)
	{
		if (root == nullptr) return root;

		Node* newnode = new Node(root->_key, root->_value);

		newnode->_left = Copy(root->_left);
		newnode->_right = Copy(root->_right);

		return newnode;
	}
	bool _IsBalance(Node* root, int blackNum, int selfBlackNum)
	{
		if (root == nullptr)
		{
			if (blackNum != selfBlackNum)
			{
				cout << "Black number error, blackNum: " << blackNum << " , selfBlackNum: " << selfBlackNum << endl;
				return false;
			}
			else
			{
				//cout << "blackNum: " << blackNum << " , selfBlackNum: " << selfBlackNum << endl;
				return true;
			}
		}

		if (root->_color == RED && root->_parent->_color == RED)
		{
			cout << "parent and cur is RED, key:" << root->_key << endl;
			return false;
		}

		if (root->_color == BLACK) selfBlackNum++;
		return _IsBalance(root->_left, blackNum, selfBlackNum) && _IsBalance(root->_right, blackNum, selfBlackNum);
	}

	void RotateR(Node* cur)
	{
		Node* parentOfcur = cur->_parent;
		Node* left = cur->_left;


		cur->_left = left->_right;
		if (left->_right)
			left->_right->_parent = cur;
		left->_right = cur;
		cur->_parent = left;
		if (parentOfcur == nullptr)
		{
			_root = left;
			left->_parent = nullptr;
		}
		else
		{

			if (parentOfcur->_left == cur)
			{
				parentOfcur->_left = left;
				left->_parent = parentOfcur;
			}
			else
			{
				parentOfcur->_right = left;
				left->_parent = parentOfcur;
			}
		}


	}

	void RotateL(Node* cur)
	{
		Node* parentOfcur = cur->_parent;
		Node* right = cur->_right;

		cur->_right = right->_left;
		if (right->_left)
			right->_left->_parent = cur;
		right->_left = cur;
		cur->_parent = right;


		if (parentOfcur == nullptr)
		{
			_root = right;
			right->_parent = nullptr;
		}
		else
		{
			if (parentOfcur->_right == cur)
			{
				parentOfcur->_right = right;
				right->_parent = parentOfcur;
			}
			else
			{
				parentOfcur->_left = right;
				right->_parent = parentOfcur;
			}
		}

	
	}

	void RotateRL(Node* cur)
	{

		Node* parentOfcur = cur->_parent;

		Node* right = cur->_right;
		Node* leftOfright = right->_left;

		RotateR(right);
		RotateL(cur);

	}

	void RotateLR(Node* cur)
	{
		Node* parentOfcur = cur->_parent;

		Node* left = cur->_left;
		Node* rightOfleft = left->_right;

		RotateL(left);
		RotateR(cur);

	}
	void _InOrder(Node* root)
	{
		if (root == nullptr) return;

		_InOrder(root->_left);

		cout << root->_key << ":" << root->_value << endl;

		_InOrder(root->_right);

	}
	Node* _root = nullptr;
};

